#include <climits>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <bitset>

using namespace std;

// 39. 组合总和
// https://leetcode.cn/problems/combination-sum/

// 解法一：每一层对每个术进行判断选或不选
class Solution {
    vector<int> path;
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> ans;
        dfs(candidates, target, ans, 0, 0);
        return ans;
    }

    void dfs(vector<int>& candidates, int target, vector<vector<int>>& ans, int sum, int pos)
    {
        if (sum == target)
        {
            ans.push_back(path);
            return;
        }

        for (int i = pos; i<candidates.size(); ++i)
        {
            if (sum + candidates[i] <= target)
            {
                path.push_back(candidates[i]);
                dfs(candidates, target, ans, sum+candidates[i], i);
                path.pop_back();
            }
        }
    }
};

// 解法二：每一层按照选多少种
class Solution {
    vector<int> path;
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> ans;
        dfs(candidates, target, ans, 0, 0);
        return ans;
    }

    void dfs(vector<int>& nums, int target, vector<vector<int>>& ans, int sum, int pos)
    {
        if (sum == target)
        {
            ans.push_back(path);
            return;
        }
        if (pos == nums.size() || sum > target) return;

        for (int i = 0; i * nums[pos] + sum <= target; ++i)
        {
            if (i != 0) path.push_back(nums[pos]);
            dfs(nums, target, ans, i * nums[pos] + sum, pos + 1);
        }

        for (int i = 1; i * nums[pos] + sum <= target; ++i)
        {
            path.pop_back();
        }
    }
};

// 784. 字母大小写全排列
// https://leetcode.cn/problems/letter-case-permutation/
class Solution {
    string path;
    vector<string> ans;
public:
    vector<string> letterCasePermutation(string s) {
        dfs(s, 0);
        return ans;
    }

    void dfs(string& s, int pos)
    {
        if (pos == s.size())
        {
            ans.push_back(path);
            return;
        }

        path.push_back(s[pos]);
        dfs(s, pos+1);
        path.pop_back();

        if (s[pos] < '0' || s[pos] > '9')
        {
            char tmp = change(s[pos]);
            path.push_back(tmp);
            dfs(s, pos+1);
            path.pop_back();
        }
    }

    char change(char ch)
    {
        if ('a' <= ch && ch <= 'z') ch -= 32;
        else ch += 32;
        return ch;
    }
};

// 526. 优美的排列
// https://leetcode.cn/problems/beautiful-arrangement/description/
class Solution {
    int ans;
    bool check[16];
public:
    int countArrangement(int n) {
        dfs(1, n);
        return ans;
    }

    void dfs(int pos, int n)
    {
        if (pos > n)
        {
            ++ans;
            return;
        }

        for (int  i = 1; i<=n; ++i)
        {
            if (!check[i] && (i%pos==0 || pos%i==0))
            {
                check[i] = true;
                dfs(pos+1, n);
                check[i] = false;
            }
        }
    }
};

// 51. N 皇后
// https://leetcode.cn/problems/n-queens/description/
class Solution {
    vector<bool> row;
    vector<bool> dig1; // 主对角
    vector<bool> dig2; // 副对角
    vector<vector<string>> ans;
    vector<string> path;
public:
    vector<vector<string>> solveNQueens(int n) {
        row.resize(n);
        dig1.resize(2*n);
        dig2.resize(2*n);
        path.resize(n);
        for (int i = 0; i<n; ++i)
            path[i].append(n, '.');
        dfs(0, n);
        return ans;
    }

    void dfs(int colpos, int n)
    {
        if (colpos == n)
        {
            ans.push_back(path);
            return;
        }

        for (int i = 0; i<n; ++i)
        {
            // y=x+b -> y-x+n=b+n
            if (!row[i] && !dig1[colpos-i+n] && !dig2[colpos+i])
            {
                row[i] = dig1[colpos-i+n] = dig2[colpos+i] = true;
                path[colpos][i] = 'Q';
                dfs(colpos+1, n);
                path[colpos][i] = '.';
                row[i] = dig1[colpos-i+n] = dig2[colpos+i] = false;
            }
        }
    }
};

// 36. 有效的数独
// https://leetcode.cn/problems/valid-sudoku/
class Solution {
    vector<bitset<10>> row;
    vector<bitset<10>> col;
    vector<vector<bitset<10>>> grid;
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        row.resize(9);
        col.resize(9);
        grid.resize(3);
        for (int i = 0; i<3; ++i)
            grid[i].resize(3);
        
        for (int i = 0; i<9; ++i)
        {
            for (int j = 0; j<9; ++j)
            {
                int num = board[i][j] - '0';
                if (1 <= num && num <= 9)
                {
                    if (row[i][num] || col[j][num] || grid[i/3][j/3][num])
                        return false;
                    row[i][num] = col[j][num] = grid[i/3][j/3][num] = 1;
                }
            }
        }
        return true;
    }
};

// 37. 解数独
// https://leetcode.cn/problems/sudoku-solver/
class Solution {
    vector<bitset<10>> row;
    vector<bitset<10>> col;
    vector<vector<bitset<10>>> grid;
public:
    void solveSudoku(vector<vector<char>>& board) {
        row.resize(9);
        col.resize(9);
        grid.resize(3);
        for (int i = 0; i<3; ++i)
            grid[i].resize(3);
        
        for (int i = 0; i<9; ++i)
        {
            for (int j = 0; j<9; ++j)
            {
                int num = board[i][j] - '0';
                if (1 <= num && num <= 9)
                {
                    row[i][num] = col[j][num] = grid[i/3][j/3][num] = 1;
                }
            }
        }

        dfs(board);
    }

    bool dfs(vector<vector<char>>& board)
    {
        for (int i = 0; i<9; ++i)
        {
            for (int j = 0; j<9; ++j)
            {
                if (board[i][j] == '.')
                {
                    for (int num = 1; num<=9; ++num)
                    {
                        if (!row[i][num] && !col[j][num] && !grid[i/3][j/3][num])
                        {
                            row[i][num] = col[j][num] = grid[i/3][j/3][num] = 1;
                            board[i][j] = num + '0';
                            bool isvalid = dfs(board);
                            if (isvalid)
                                return true;
                            else
                            {
                                row[i][num] = col[j][num] = grid[i/3][j/3][num] = 0;
                                board[i][j] = '.';
                            }
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
};

// 79. 单词搜索
// https://leetcode.cn/problems/word-search/
class Solution {
    int check[7][7];
    int dx[4] = { 0,0,-1,1 };
    int dy[4] = { -1,1,0,0 };
    int n, m;
public:
    bool exist(vector<vector<char>>& board, string word) {
        n = board.size();
        m = board[0].size();
        for (int i = 0; i<n; ++i)
        {
            for (int j = 0; j<m; ++j)
            {
                if (board[i][j] == word[0])
                {
                    check[i][j] = true;
                    if (dfs(board, word, i, j, 1))
                        return true;
                    check[i][j] = false;
                }
            }
        }
        return false;
    }

    bool dfs(vector<vector<char>>& board, string& word, int y, int x, int pos)
    {
        if (pos == word.size())
            return true;

        for (int i = 0; i<4; ++i)
        {
            int _x = x + dx[i];
            int _y = y + dy[i];
            if (0<=_y && _y<n && 0<=_x && _x<m && !check[_y][_x] && board[_y][_x] == word[pos])
            {
                check[_y][_x] = true;
                if (dfs(board, word, _y, _x, pos+1))
                    return true;
                check[_y][_x] = false;
            }
        }
        return false;
    }
};